home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer)…68k, x86, SPARC, PA-RISC] / NeXTSTEP 3.3 Dev Intel.iso / NextDeveloper / Source / GNU / cctools / as / hash.c < prev    next >
C/C++ Source or Header  |  1994-02-24  |  31KB  |  1,063 lines
  1. /* hash.c - hash table lookup strings -
  2.    Copyright (C) 1987 Free Software Foundation, Inc.
  3.  
  4. This file is part of GAS, the GNU Assembler.
  5.  
  6. GAS is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 1, or (at your option)
  9. any later version.
  10.  
  11. GAS is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GAS; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20. /*
  21.  * BUGS, GRIPES, APOLOGIA etc.
  22.  *
  23.  * A typical user doesn't need ALL this: I intend to make a library out
  24.  * of it one day - Dean Elsner.
  25.  * Also, I want to change the definition of a symbol to (address,length)
  26.  * so I can put arbitrary binary in the names stored. [see hsh.c for that]
  27.  *
  28.  * This slime is common coupled inside the module. Com-coupling (and other
  29.  * vandalism) was done to speed running time. The interfaces at the
  30.  * module's edges are adequately clean.
  31.  *
  32.  * There is no way to (a) run a test script through this heap and (b)
  33.  * compare results with previous scripts, to see if we have broken any
  34.  * code. Use GNU (f)utilities to do this. A few commands assist test.
  35.  * The testing is awkward: it tries to be both batch & interactive.
  36.  * For now, interactive rules!
  37.  */
  38.  
  39. /*
  40.  *  The idea is to implement a symbol table. A test jig is here.
  41.  *  Symbols are arbitrary strings; they can't contain '\0'.
  42.  *    [See hsh.c for a more general symbol flavour.]
  43.  *  Each symbol is associated with a char*, which can point to anything
  44.  *  you want, allowing an arbitrary property list for each symbol.
  45.  *
  46.  *  The basic operations are:
  47.  *
  48.  *    new                     creates symbol table, returns handle
  49.  *    find (symbol)           returns char*
  50.  *    insert (symbol,char*)   error if symbol already in table
  51.  *    delete (symbol)         returns char* if symbol was in table
  52.  *    apply                   so you can delete all symbols before die()
  53.  *    die                     destroy symbol table (free up memory)
  54.  *
  55.  *  Supplementary functions include:
  56.  *
  57.  *    say                     how big? what % full?
  58.  *    replace (symbol,newval) report previous value
  59.  *    jam (symbol,value)      assert symbol:=value
  60.  *
  61.  *  You, the caller, have control over errors: this just reports them.
  62.  *
  63.  *  This package requires malloc(), free().
  64.  *  Malloc(size) returns NULL or address of char[size].
  65.  *  Free(address) frees same.
  66.  */
  67.  
  68. /*
  69.  *  The code and its structures are re-enterent.
  70.  *  Before you do anything else, you must call hash_new() which will
  71.  *  return the address of a hash-table-control-block (or NULL if there
  72.  *  is not enough memory). You then use this address as a handle of the
  73.  *  symbol table by passing it to all the other hash_...() functions.
  74.  *  The only approved way to recover the memory used by the symbol table
  75.  *  is to call hash_die() with the handle of the symbol table.
  76.  *
  77.  *  Before you call hash_die() you normally delete anything pointed to
  78.  *  by individual symbols. After hash_die() you can't use that symbol
  79.  *  table again.
  80.  *
  81.  *  The char* you associate with a symbol may not be NULL (0) because
  82.  *  NULL is returned whenever a symbol is not in the table. Any other
  83.  *  value is OK, except DELETED, #defined below.
  84.  *
  85.  *  When you supply a symbol string for insertion, YOU MUST PRESERVE THE
  86.  *  STRING until that symbol is deleted from the table. The reason is that
  87.  *  only the address you supply, NOT the symbol string itself, is stored
  88.  *  in the symbol table.
  89.  *
  90.  *  You may delete and add symbols arbitrarily.
  91.  *  Any or all symbols may have the same 'value' (char *). In fact, these
  92.  *  routines don't do anything with your symbol values.
  93.  *
  94.  *  You have no right to know where the symbol:char* mapping is stored,
  95.  *  because it moves around in memory; also because we may change how it
  96.  *  works and we don't want to break your code do we? However the handle
  97.  *  (address of struct hash_control) is never changed in
  98.  *  the life of the symbol table.
  99.  *
  100.  *  What you CAN find out about a symbol table is:
  101.  *    how many slots are in the hash table?
  102.  *    how many slots are filled with symbols?
  103.  *    (total hashes,collisions) for (reads,writes) (*)
  104.  *  All of the above values vary in time.
  105.  *  (*) some of these numbers will not be meaningful if we change the
  106.  *  internals.
  107.  */
  108.  
  109. /*
  110.  *  I N T E R N A L
  111.  *
  112.  *  Hash table is an array of hash_entries; each entry is a pointer to a
  113.  *  a string and a user-supplied value 1 char* wide.
  114.  *
  115.  *  The array always has 2 ** n elements, n>0, n integer.
  116.  *  There is also a 'wall' entry after the array, which is always empty
  117.  *  and acts as a sentinel to stop running off the end of the array.
  118.  *  When the array gets too full, we create a new array twice as large
  119.  *  and re-hash the symbols into the new array, then forget the old array.
  120.  *  (Of course, we copy the values into the new array before we junk the
  121.  *  old array!)
  122.  *
  123.  */
  124.  
  125. #include <stdio.h>
  126. #include <stdlib.h>
  127. #include <ctype.h>
  128. #include "hash.h"
  129. #include "xmalloc.h"
  130. #include "messages.h"
  131.  
  132. #define TRUE           (1)
  133. #define FALSE          (0)
  134. #define min(a, b)    ((a) < (b) ? (a) : (b))
  135.  
  136.  
  137. #define DELETED     ((char *)1)    /* guarenteed invalid address */
  138. #define START_POWER    (11)    /* power of two: size of new hash table *//* JF was 6 */
  139. /* JF These next two aren't used any more. */
  140. /* #define START_SIZE    (64)    / * 2 ** START_POWER */
  141. /* #define START_FULL    (32)      / * number of entries before table expands */
  142. #define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED)
  143.                 /* above TRUE if a symbol is in entry @ ptr */
  144.  
  145. #define STAT_SIZE      (0)      /* number of slots in hash table */
  146.                 /* the wall does not count here */
  147.                 /* we expect this is always a power of 2 */
  148. #define STAT_ACCESS    (1)    /* number of hash_ask()s */
  149. #define STAT__READ     (0)      /* reading */
  150. #define STAT__WRITE    (1)      /* writing */
  151. #define STAT_COLLIDE   (3)    /* number of collisions (total) */
  152.                 /* this may exceed STAT_ACCESS if we have */
  153.                 /* lots of collisions/access */
  154. #define STAT_USED      (5)    /* slots used right now */
  155. #define STATLENGTH     (6)    /* size of statistics block */
  156. #if STATLENGTH != HASH_STATLENGTH
  157. Panic! Please make #include "stat.h" agree with previous definitions!
  158. #endif
  159.  
  160. /* #define SUSPECT to do runtime checks */
  161. /* #define TEST to be a test jig for hash...() */
  162.  
  163. #ifdef TEST            /* TEST: use smaller hash table */
  164. #undef  START_POWER
  165. #define START_POWER (3)
  166. #undef  START_SIZE
  167. #define START_SIZE  (8)
  168. #undef  START_FULL
  169. #define START_FULL  (4)
  170. static void hash_die(
  171.     struct hash_control *handle);
  172. static void hash_say(
  173.     struct hash_control *handle,
  174.     int buffer[/*bufsiz*/],
  175.     int bufsiz);
  176. static char *hash_delete(        /* previous value         */
  177.     struct hash_control *handle,
  178.     char *string);
  179. static char *hash_replace(        /* previous value         */
  180.     struct hash_control *handle,
  181.     char *string,
  182.     char *value);
  183. #endif /* TEST */
  184.  
  185. /*------------------ plan ---------------------------------- i = internal
  186.  
  187. struct hash_control * c;
  188. struct hash_entry   * e;                                                    i
  189. int                   b[z];     buffer for statistics
  190.                       z         size of b
  191. char                * s;        symbol string (address) [ key ]
  192. char                * v;        value string (address)  [datum]
  193. boolean               f;        TRUE if we found s in hash table            i
  194. char                * t;        error string; "" means OK
  195. int                   a;        access type [0...n)                         i
  196.  
  197. c=hash_new       ()             create new hash_control
  198.  
  199. hash_die         (c)            destroy hash_control (and hash table)
  200.                                 table should be empty.
  201.                                 doesn't check if table is empty.
  202.                                 c has no meaning after this.
  203.  
  204. hash_say         (c,b,z)        report statistics of hash_control.
  205.                                 also report number of available statistics.
  206.  
  207. v=hash_delete    (c,s)          delete symbol, return old value if any.
  208.     ask()                       NULL means no old value.
  209.     f
  210.  
  211. v=hash_replace   (c,s,v)        replace old value of s with v.
  212.     ask()                       NULL means no old value: no table change.
  213.     f
  214.  
  215. t=hash_insert    (c,s,v)        insert (s,v) in c.
  216.     ask()                       return error string.
  217.     f                           it is an error to insert if s is already
  218.                                 in table.
  219.                                 if any error, c is unchanged.
  220.  
  221. t=hash_jam       (c,s,v)        assert that new value of s will be v.       i
  222.     ask()                       it may decide to GROW the table.            i
  223.     f                                                                       i
  224.     grow()                                                                  i
  225. t=hash_grow      (c)            grow the hash table.                        i
  226.     jam()                       will invoke JAM.                            i
  227.  
  228. ?=hash_apply     (c,y)          apply y() to every symbol in c.
  229.     y                           evtries visited in 'unspecified' order.
  230.  
  231. v=hash_find      (c,s)          return value of s, or NULL if s not in c.
  232.     ask()
  233.     f
  234.  
  235. f,e=hash_ask()   (c,s,a)        return slot where s SHOULD live.            i
  236.     code()                      maintain collision stats in c.              i
  237.  
  238. .=hash_code      (c,s)          compute hash-code for s,                    i
  239.                                 from parameters of c.                       i
  240.  
  241. */
  242.  
  243. static char hash_found;        /* returned by hash_ask() to stop extra */
  244.                 /* testing. hash_ask() wants to return both */
  245.                 /* a slot and a status. This is the status. */
  246.                 /* TRUE: found symbol */
  247.                 /* FALSE: absent: empty or deleted slot */
  248.                 /* Also returned by hash_jam(). */
  249.                 /* TRUE: we replaced a value */
  250.                 /* FALSE: we inserted a value */
  251.  
  252. static struct hash_entry *hash_ask(
  253.     struct hash_control *handle,
  254.     char *string,
  255.     int access);
  256. static int hash_code(
  257.     struct hash_control *handle,
  258.     char *string);
  259. static char *hash_grow(
  260.     struct hash_control *handle);
  261.  
  262. /*
  263.  *             h a s h _ n e w ( )
  264.  *
  265.  */
  266. struct hash_control *
  267. hash_new(void)            /* create a new hash table */
  268.                 /* return NULL if failed */
  269.                 /* return handle (address of struct hash) */
  270. {
  271.   register struct hash_control * retval;
  272.   register struct hash_entry *   room;    /* points to hash table */
  273.   register struct hash_entry *   wall;
  274.   register struct hash_entry *   entry;
  275.   register int *                 ip;    /* scan stats block of struct hash_control */
  276.   register int *                 nd;    /* limit of stats block */
  277.  
  278.   if ((room = (struct hash_entry *) malloc( sizeof(struct hash_entry)*((1<<START_POWER) + 1) ) ))
  279.                 /* +1 for the wall entry */
  280.     {
  281.       if ((retval = (struct hash_control *) malloc(sizeof(struct hash_control)) ))
  282.     {
  283.       nd = retval->hash_stat + STATLENGTH;
  284.       for (ip=retval->hash_stat; ip<nd; ip++)
  285.         {
  286.           *ip = 0;
  287.         }
  288.  
  289.       retval -> hash_stat[STAT_SIZE]  = 1<<START_POWER;
  290.       retval -> hash_mask             = (1<<START_POWER) - 1;
  291.       retval -> hash_sizelog      = START_POWER;
  292.                 /* works for 1's compl ok */
  293.       retval -> hash_where            = room;
  294.       retval -> hash_wall             =
  295.         wall                          = room + (1<<START_POWER);
  296.       retval -> hash_full             = (1<<START_POWER)/2;
  297.       for (entry=room; entry<=wall; entry++)
  298.         {
  299.           entry->hash_string = NULL;
  300.         }
  301.     }
  302.     }
  303.   else
  304.     {
  305.       retval = NULL;        /* no room for table: fake a failure */
  306.     }
  307.   return(retval);        /* return NULL or set-up structs */
  308. }
  309.  
  310. #ifdef TEST
  311. /*
  312.  *           h a s h _ d i e ( )
  313.  *
  314.  * Table should be empty, but this is not checked.
  315.  * To empty the table, try hash_apply()ing a symbol deleter.
  316.  * Return to free memory both the hash table and it's control
  317.  * block.
  318.  * 'handle' has no meaning after this function.
  319.  * No errors are recoverable.
  320.  */
  321. static
  322. void
  323. hash_die(
  324. struct hash_control *handle)
  325. {
  326.   free((char *)handle->hash_where);
  327.   free((char *)handle);
  328. }
  329.  
  330. /*
  331.  *           h a s h _ s a y ( )
  332.  *
  333.  * Return the size of the statistics table, and as many statistics as
  334.  * we can until either (a) we have run out of statistics or (b) caller
  335.  * has run out of buffer.
  336.  * NOTE: hash_say treats all statistics alike.
  337.  * These numbers may change with time, due to insertions, deletions
  338.  * and expansions of the table.
  339.  * The first "statistic" returned is the length of hash_stat[].
  340.  * Then contents of hash_stat[] are read out (in ascending order)
  341.  * until your buffer or hash_stat[] is exausted.
  342.  */
  343. static
  344. void
  345. hash_say(
  346. struct hash_control *handle,
  347. int buffer[/*bufsiz*/],
  348. int bufsiz)
  349. {
  350.   register int * nd;            /* limit of statistics block */
  351.   register int * ip;            /* scan statistics */
  352.  
  353.   ip = handle -> hash_stat;
  354.   nd = ip + min(bufsiz-1,STATLENGTH);
  355.   if (bufsiz>0)            /* trust nothing! bufsiz<=0 is dangerous */
  356.     {
  357.       *buffer++ = STATLENGTH;
  358.       for (; ip<nd; ip++,buffer++)
  359.     {
  360.       *buffer = *ip;
  361.     }
  362.     }
  363. }
  364.  
  365. /*
  366.  *           h a s h _ d e l e t e ( )
  367.  *
  368.  * Try to delete a symbol from the table.
  369.  * If it was there, return its value (and adjust STAT_USED).
  370.  * Otherwise, return NULL.
  371.  * Anyway, the symbol is not present after this function.
  372.  *
  373.  */
  374. static
  375. char *                /* NULL if string not in table, else */
  376. hash_delete(            /* returns value of deleted symbol */
  377. struct hash_control *handle,
  378. char *string)
  379. {
  380.   register char *                   retval; /* NULL if string not in table */
  381.   register struct hash_entry *      entry; /* NULL or entry of this symbol */
  382.  
  383.   entry = hash_ask(handle,string,STAT__WRITE);
  384.   if (hash_found)
  385.     {
  386.       retval = entry -> hash_value;
  387.       entry -> hash_string = DELETED; /* mark as deleted */
  388.       handle -> hash_stat[STAT_USED] -= 1; /* slots-in-use count */
  389. #ifdef SUSPECT
  390.       if (handle->hash_stat[STAT_USED]<0)
  391.         {
  392. #ifdef NeXT
  393.           as_fatal("hash_delete");
  394. #else
  395.           error("hash_delete");
  396. #endif
  397.         }
  398. #endif /* def SUSPECT */
  399.     }
  400.   else
  401.     {
  402.       retval = NULL;
  403.     }
  404.   return(retval);
  405. }
  406.  
  407. /*
  408.  *                   h a s h _ r e p l a c e ( )
  409.  *
  410.  * Try to replace the old value of a symbol with a new value.
  411.  * Normally return the old value.
  412.  * Return NULL and don't change the table if the symbol is not already
  413.  * in the table.
  414.  */
  415. static
  416. char *
  417. hash_replace(
  418. struct hash_control *handle,
  419. char *string,
  420. char *value)
  421. {
  422.   register struct hash_entry *      entry;
  423.   register char *                   retval;
  424.  
  425.   entry = hash_ask(handle,string,STAT__WRITE);
  426.   if (hash_found)
  427.     {
  428.       retval = entry -> hash_value;
  429.       entry -> hash_value = value;
  430.     }
  431.   else
  432.     {
  433.       retval = NULL;
  434.     }
  435.   ;
  436.   return (retval);
  437. }
  438. #endif /* TEST */
  439.  
  440. /*
  441.  *                   h a s h _ i n s e r t ( )
  442.  *
  443.  * Insert a (symbol-string, value) into the hash table.
  444.  * Return an error string, "" means OK.
  445.  * It is an 'error' to insert an existing symbol.
  446.  */
  447. char *                /* return error string */
  448. hash_insert(
  449. struct hash_control *handle,
  450. char *string,
  451. char *value)
  452. {
  453.   register struct hash_entry * entry;
  454.   register char *              retval;
  455.  
  456.   retval = "";
  457.   if (handle->hash_stat[STAT_USED] > handle->hash_full)
  458.     {
  459.       retval = hash_grow(handle);
  460.     }
  461.   if ( ! * retval)
  462.     {
  463.       entry = hash_ask(handle,string,STAT__WRITE);
  464.       if (hash_found)
  465.     {
  466.       retval = "exists";
  467.     }
  468.       else
  469.     {
  470.       entry -> hash_value  = value;
  471.       entry -> hash_string = string;
  472.       handle-> hash_stat[STAT_USED]  += 1;
  473.     }
  474.     }
  475.   return(retval);
  476. }
  477.  
  478. /*
  479.  *               h a s h _ j a m ( )
  480.  *
  481.  * Regardless of what was in the symbol table before, after hash_jam()
  482.  * the named symbol has the given value. The symbol is either inserted or
  483.  * (its value is) relpaced.
  484.  * An error message string is returned, "" means OK.
  485.  *
  486.  * WARNING: this may decide to grow the hashed symbol table.
  487.  * To do this, we call hash_grow(), WHICH WILL recursively CALL US.
  488.  *
  489.  * We report status internally: hash_found is TRUE if we replaced, but
  490.  * false if we inserted.
  491.  */
  492. char *
  493. hash_jam(
  494. struct hash_control *handle,
  495. char *string,
  496. char *value)
  497. {
  498.   register char *                   retval;
  499.   register struct hash_entry *      entry;
  500.  
  501.   retval = "";
  502.   if (handle->hash_stat[STAT_USED] > handle->hash_full)
  503.     {
  504.       retval = hash_grow(handle);
  505.     }
  506.   if (! * retval)
  507.     {
  508.       entry = hash_ask(handle,string,STAT__WRITE);
  509.       if ( ! hash_found)
  510.     {
  511.       entry -> hash_string = string;
  512.       handle->hash_stat[STAT_USED] += 1;
  513.     }
  514.       entry -> hash_value = value;
  515.     }
  516.   return(retval);
  517. }
  518.  
  519. /*
  520.  *               h a s h _ g r o w ( )
  521.  *
  522.  * Grow a new (bigger) hash table from the old one.
  523.  * We choose to double the hash table's size.
  524.  * Return a human-scrutible error string: "" if OK.
  525.  * Warning! This uses hash_jam(), which had better not recurse
  526.  * back here! Hash_jam() conditionally calls us, but we ALWAYS
  527.  * call hash_jam()!
  528.  * Internal.
  529.  */
  530. static
  531. char *
  532. hash_grow(        /* make a hash table grow */
  533. struct hash_control *handle)
  534. {
  535.   register struct hash_entry *      newwall;
  536.   register struct hash_entry *      newwhere;
  537.   struct hash_entry *      newtrack;
  538.   register struct hash_entry *      oldtrack;
  539.   register struct hash_entry *      oldwhere;
  540.   register struct hash_entry *      oldwall;
  541.   register int                      temp;
  542.   int                      newsize;
  543.   char *                   string;
  544.   char *                   retval;
  545. #ifdef SUSPECT
  546.   int                      oldused;
  547. #endif
  548.  
  549.   /*
  550.    * capture info about old hash table
  551.    */
  552.   oldwhere = handle -> hash_where;
  553.   oldwall  = handle -> hash_wall;
  554. #ifdef SUSPECT
  555.   oldused  = handle -> hash_stat[STAT_USED];
  556. #endif
  557.   /*
  558.    * attempt to get enough room for a hash table twice as big
  559.    */
  560.   temp = handle->hash_stat[STAT_SIZE];
  561.   if ((newwhere = (struct hash_entry *) xmalloc((long)((temp+temp+1)*sizeof(struct hash_entry)))))
  562.                 /* +1 for wall slot */
  563.     {
  564.       retval = "";        /* assume success until proven otherwise */
  565.       /*
  566.        * have enough room: now we do all the work.
  567.        * double the size of everything in handle,
  568.        * note: hash_mask frob works for 1's & for 2's complement machines
  569.        */
  570.       handle->hash_mask              = handle->hash_mask + handle->hash_mask + 1;
  571.       handle->hash_stat[STAT_SIZE] <<= 1;
  572.       newsize                        = handle->hash_stat[STAT_SIZE];
  573.       handle->hash_where             = newwhere;
  574.       handle->hash_full            <<= 1;
  575.       handle->hash_sizelog        += 1;
  576.       handle->hash_stat[STAT_USED]   = 0;
  577.       handle->hash_wall              =
  578.       newwall                        = newwhere + newsize;
  579.       /*
  580.        * set all those pesky new slots to vacant.
  581.        */
  582.       for (newtrack=newwhere; newtrack < newwall; newtrack++)
  583.     {
  584.       newtrack -> hash_string = NULL;
  585.     }
  586.       /*
  587.        * we will do a scan of the old table, the hard way, using the
  588.        * new control block to re-insert the data into new hash table.
  589.        */
  590.       handle -> hash_stat[STAT_USED] = 0;    /* inserts will bump it up to correct */
  591.       for (oldtrack=oldwhere; oldtrack < oldwall; oldtrack++)
  592.     {
  593.       if ( (string=oldtrack->hash_string) && string!=DELETED )
  594.         {
  595.           if ( * (retval = hash_jam(handle,string,oldtrack->hash_value) ) )
  596.         {
  597.           break;
  598.         }
  599.         }
  600.     }
  601. #ifdef SUSPECT
  602.       if ( !*retval && handle->hash_stat[STAT_USED] != oldused)
  603.     {
  604.       retval = "hash_used";
  605.     }
  606. #endif
  607.       if (!*retval)
  608.     {
  609.       /*
  610.        * we have a completely faked up control block.
  611.        * return the old hash table.
  612.        */
  613.       free((char *)oldwhere);
  614.       /*
  615.        * Here with success. retval is already "".
  616.        */
  617.     }
  618.     }
  619.   else
  620.     {
  621.       retval = "no room";
  622.     }
  623.   return(retval);
  624. }
  625.  
  626. /*
  627.  *          h a s h _ a p p l y ( )
  628.  *
  629.  * Use this to scan each entry in symbol table.
  630.  * For each symbol, this calls (applys) a nominated function supplying the
  631.  * symbol's value (and the symbol's name).
  632.  * The idea is you use this to destroy whatever is associted with
  633.  * any values in the table BEFORE you destroy the table with hash_die.
  634.  * Of course, you can use it for other jobs; whenever you need to
  635.  * visit all extant symbols in the table.
  636.  *
  637.  * We choose to have a call-you-back idea for two reasons:
  638.  *  asthetic: it is a neater idea to use apply than an explicit loop
  639.  *  sensible: if we ever had to grow the symbol table (due to insertions)
  640.  *            then we would lose our place in the table when we re-hashed
  641.  *            symbols into the new table in a different order.
  642.  *
  643.  * The order symbols are visited depends entirely on the hashing function.
  644.  * Whenever you insert a (symbol, value) you risk expanding the table. If
  645.  * you do expand the table, then the hashing function WILL change, so you
  646.  * MIGHT get a different order of symbols visited. In other words, if you
  647.  * want the same order of visiting symbols as the last time you used
  648.  * hash_apply() then you better not have done any hash_insert()s or
  649.  * hash_jam()s since the last time you used hash_apply().
  650.  *
  651.  * In future we may use the value returned by your nominated function.
  652.  * One idea is to abort the scan if, after applying the function to a
  653.  * certain node, the function returns a certain code.
  654.  * To be safe, please make your functions of type char *. If you always
  655.  * return NULL, then the scan will complete, visiting every symbol in
  656.  * the table exactly once. ALL OTHER RETURNED VALUES have no meaning yet!
  657.  * Caveat Actor!
  658.  *
  659.  * The function you supply should be of the form:
  660.  *      char * myfunct(string,value)
  661.  *              char * string;        |* the symbol's name *|
  662.  *              char * value;         |* the symbol's value *|
  663.  *      {
  664.  *        |* ... *|
  665.  *        return(NULL);
  666.  *      }
  667.  *
  668.  * The returned value of hash_apply() is (char*)NULL. In future it may return
  669.  * other values. NULL means "completed scan OK". Other values have no meaning
  670.  * yet. (The function has no graceful failures.)
  671.  */
  672. char *
  673. hash_apply(
  674. struct hash_control *handle,
  675. char *(*function)(char *hash_string, char *hash_value))
  676. {
  677.   register struct hash_entry *      entry;
  678.   register struct hash_entry *      wall;
  679.  
  680.   wall = handle->hash_wall;
  681.   for (entry = handle->hash_where; entry < wall; entry++)
  682.     {
  683.       if (islive(entry))    /* silly code: tests entry->string twice! */
  684.     {
  685.       (*function)(entry->hash_string,entry->hash_value);
  686.     }
  687.     }
  688.   return (NULL);
  689. }
  690.  
  691. /*
  692.  *          h a s h _ f i n d ( )
  693.  *
  694.  * Given symbol string, find value (if any).
  695.  * Return found value or NULL.
  696.  */
  697. char *
  698. hash_find(
  699. struct hash_control *handle,
  700. char *string)
  701. {
  702.   register struct hash_entry *      entry;
  703.   register char *                   retval;
  704.  
  705.   entry = hash_ask(handle,string,STAT__READ);
  706.   if (hash_found)
  707.     {
  708.       retval = entry->hash_value;
  709.     }
  710.   else
  711.     {
  712.       retval = NULL;
  713.     }
  714.   return(retval);
  715. }
  716.  
  717. /*
  718.  *          h a s h _ a s k ( )
  719.  *
  720.  * Searches for given symbol string.
  721.  * Return the slot where it OUGHT to live. It may be there.
  722.  * Return hash_found: TRUE only if symbol is in that slot.
  723.  * Access argument is to help keep statistics in control block.
  724.  * Internal.
  725.  */
  726. static
  727. struct hash_entry *    /* string slot, may be empty or deleted */
  728. hash_ask(
  729. struct hash_control * handle,
  730. char *                string,
  731. int                   access) /* access type */
  732. {
  733.   register char    *string1;    /* JF avoid strcmp calls */
  734.   register char *                   s;
  735.   register int                      c;
  736.   register struct hash_entry *      slot;
  737.   register int                      collision; /* count collisions */
  738.  
  739.   slot = handle->hash_where + hash_code(handle,string); /* start looking here */
  740.   handle->hash_stat[STAT_ACCESS+access] += 1;
  741.   collision = 0;
  742.   hash_found = FALSE;
  743.   while ( (s = slot->hash_string) && s!=DELETED )
  744.     {
  745.         for(string1=string;;) {
  746.         if(!(c= *s++)) {
  747.             if(!*string1)
  748.                 hash_found = TRUE;
  749.             break;
  750.         }
  751.         if(*string1++!=c)
  752.             break;
  753.     }
  754.     if(hash_found)
  755.         break;
  756.       collision++;
  757.       slot++;
  758.     }
  759.   /*
  760.    * slot:                                                      return:
  761.    *       in use:     we found string                           slot
  762.    *       at empty:
  763.    *                   at wall:        we fell off: wrap round   ????
  764.    *                   in table:       dig here                  slot
  765.    *       at DELETED: dig here                                  slot
  766.    */
  767.   if (slot==handle->hash_wall)
  768.     {
  769.       slot = handle->hash_where; /* now look again */
  770.       while( (s = slot->hash_string) && s!=DELETED )
  771.     {
  772.       for(string1=string;*s;string1++,s++) {
  773.         if(*string1!=*s)
  774.         break;
  775.       }
  776.       if(*s==*string1) {
  777.           hash_found = TRUE;
  778.           break;
  779.         }
  780.       collision++;
  781.       slot++;
  782.     }
  783.       /*
  784.        * slot:                                                   return:
  785.        *       in use: we found it                                slot
  786.        *       empty:  wall:         ERROR IMPOSSIBLE             !!!!
  787.        *               in table:     dig here                     slot
  788.        *       DELETED:dig here                                   slot
  789.        */
  790.     }
  791. /*   fprintf(stderr,"hash_ask(%s)->%d(%d)\n",string,hash_code(handle,string),collision); */
  792.   handle -> hash_stat[STAT_COLLIDE+access] += collision;
  793.   return(slot);            /* also return hash_found */
  794. }
  795.  
  796. /*
  797.  *           h a s h _ c o d e
  798.  *
  799.  * Does hashing of symbol string to hash number.
  800.  * Internal.
  801.  */
  802. static
  803. int
  804. hash_code(
  805. struct hash_control *handle,
  806. char *string)
  807. {
  808.   register long int                 h;      /* hash code built here */
  809.   register long int                 c;      /* each character lands here */
  810.   register int               n;      /* Amount to shift h by */
  811.  
  812.   n = (handle->hash_sizelog - 3);
  813.   h = 0;
  814.   while((c = *string++))
  815.     {
  816.       h += c;
  817.       h = (h<<3) + (h>>n) + c;
  818.     }
  819.   return (h & handle->hash_mask);
  820. }
  821.  
  822. /*
  823.  * Here is a test program to exercise above.
  824.  */
  825. #ifdef TEST
  826.  
  827. #define TABLES (6)        /* number of hash tables to maintain */
  828.                 /* (at once) in any testing */
  829. #define STATBUFSIZE (12)    /* we can have 12 statistics */
  830.  
  831. int statbuf[STATBUFSIZE];    /* display statistics here */
  832. char answer[100];        /* human farts here */
  833. struct hash_control *
  834.     hashtable[TABLES];    /* we test many hash tables at once */
  835. struct hash_control * h;    /* points to curent hash_control */
  836. struct hash_control ** pp;
  837. struct hash_control *  p;
  838. char *  name;
  839. char *  value;
  840. int     size;
  841. int     used;
  842. char    command;
  843. int     number;            /* number 0:TABLES-1 of current hashed */
  844.                 /* symbol table */
  845. static char *what(
  846.     char * description);
  847. static char *destroy(
  848.     char * string,
  849.     char * value);
  850. static char *applicatee(
  851.     char * string,
  852.     char * value);
  853. static void whattable(
  854.     void);
  855.  
  856. main()
  857. {
  858.   int *  ip;
  859.   char * error;
  860.   char * thing;
  861.  
  862.   number = 0;
  863.   h = NULL;
  864.   printf("type h <RETURN> for help\n");
  865.   for(;;)
  866.     {
  867.       printf("hash_test command: ");
  868.       gets(answer);
  869.       command = answer[0];
  870.       if (isupper(command)) command = tolower(command);    /* ecch! */
  871.       switch (command)
  872.     {
  873.     case '#':
  874.       printf("old hash table #=%d.\n",number);
  875.       whattable();
  876.       break;
  877.     case '?':
  878.       for (pp=hashtable; pp<hashtable+TABLES; pp++)
  879.         {
  880.           printf("address of hash table #%d control block is %xx\n"
  881.              ,pp-hashtable,*pp);
  882.         }
  883.       break;
  884.     case 'a':
  885.       hash_apply(h,applicatee);
  886.       break;
  887.     case 'd':
  888.       hash_apply(h,destroy);
  889.       hash_die(h);
  890.       break;
  891.     case 'f':
  892.       thing = hash_find(h,name=what("symbol"));
  893.       printf("value of \"%s\" is \"%s\"\n",name,thing?thing:"NOT-PRESENT");
  894.       break;
  895.     case 'h':
  896.       printf("# show old, select new default hash table number\n");
  897.       printf("? display all hashtable control block addresses\n");
  898.       printf("a apply a simple display-er to each symbol in table\n");
  899.       printf("d die: destroy hashtable\n");
  900.       printf("f find value of nominated symbol\n");
  901.       printf("h this help\n");
  902.       printf("i insert value into symbol\n");
  903.       printf("j jam value into symbol\n");
  904.       printf("n new hashtable\n");
  905.       printf("r replace a value with another\n");
  906.       printf("s say what %% of table is used\n");
  907.       printf("q exit this program\n");
  908.       printf("x delete a symbol from table, report its value\n");
  909.       break;
  910.     case 'i':
  911.       error = hash_insert(h,name=what("symbol"),value=what("value"));
  912.       if(*error)
  913.         {
  914.           printf("symbol=\"%s\"  value=\"%s\"  error=%s\n",name,value,error);
  915.         }
  916.       break;
  917.     case 'j':
  918.       error = hash_jam(h,name=what("symbol"),value=what("value"));
  919.       if (*error)
  920.         {
  921.           printf("symbol=\"%s\"  value=\"%s\"  error=%s\n",name,value,error);
  922.         }
  923.       break;
  924.     case 'n':
  925.       h = hashtable[number] = hash_new();
  926.       break;
  927.     case 'q':
  928.       exit(0);
  929.     case 'r':
  930.       thing = hash_replace(h,name=what("symbol"),value=what("value"));
  931.       printf("old value was \"%s\"\n",thing?thing:"{}");
  932.       break;
  933.     case 's':
  934.       hash_say(h,statbuf,STATBUFSIZE);
  935.       for (ip=statbuf; ip<statbuf+STATBUFSIZE; ip++)
  936.         {
  937.           printf("%d ",*ip);
  938.         }
  939.       printf("\n");
  940.       break;
  941.     case 'x':
  942.       thing = hash_delete(h,name=what("symbol"));
  943.       printf("old value was \"%s\"\n",thing?thing:"{}");
  944.       break;
  945.     default:
  946.       printf("I can't understand command \"%c\"\n",command);
  947.       break;
  948.     }
  949.     }
  950. }
  951.  
  952. static
  953. char *
  954. what(
  955. char * description)
  956. {
  957.   char * retval;
  958.  
  959.   printf("   %s : ",description);
  960.   gets(answer);
  961.   /* will one day clean up answer here */
  962.   retval = malloc(strlen(answer)+1);
  963.   if (!retval)
  964.     {
  965. #ifdef NeXT
  966.       as_fatal("room");
  967. #else
  968.       error("room");
  969. #endif
  970.     }
  971.   (void)strcpy(retval,answer);
  972.   return(retval);
  973. }
  974.  
  975. static
  976. char *
  977. destroy(
  978. char * string,
  979. char * value)
  980. {
  981.   free(string);
  982.   free(value);
  983.   return(NULL);
  984. }
  985.  
  986. static
  987. char *
  988. applicatee(
  989. char * string,
  990. char * value)
  991. {
  992.   printf("%.20s-%.20s\n",string,value);
  993.   return(NULL);
  994. }
  995.  
  996. static
  997. void
  998. whattable(            /* determine number: what hash table to use */
  999. void)                /* also determine h: points to hash_control */
  1000. {
  1001.  
  1002.   for (;;)
  1003.     {
  1004.       printf("   what hash table (%d:%d) ?  ",0,TABLES-1);
  1005.       gets(answer);
  1006.       sscanf(answer,"%d",&number);
  1007.       if (number>=0 && number<TABLES)
  1008.     {
  1009.       h = hashtable[number];
  1010.       if (!h)
  1011.         {
  1012.           printf("warning: current hash-table-#%d. has no hash-control\n",number);
  1013.         }
  1014.       return;
  1015.     }
  1016.       else
  1017.     {
  1018.       printf("invalid hash table number: %d\n",number);
  1019.     }
  1020.     }
  1021. }
  1022.  
  1023. void *
  1024. xmalloc(
  1025. long n)
  1026. {
  1027.     void *retval;
  1028.  
  1029.     if(!(retval = malloc((unsigned)n))){
  1030.         printf("virtual memory exceeded\n");
  1031.         exit(1);
  1032.     }
  1033.     return(retval);
  1034. }
  1035.  
  1036. void *
  1037. xrealloc(
  1038. void *ptr,
  1039. long n)
  1040. {
  1041.     if((ptr = realloc(ptr, (unsigned)n)) == 0){
  1042.     printf("virtual memory exceeded\n");
  1043.     exit(1);
  1044.     }
  1045.     return(ptr);
  1046. }
  1047.  
  1048. void
  1049. as_fatal(
  1050. const char *format,
  1051. ...)
  1052. {
  1053.     va_list ap;
  1054.  
  1055.     va_start(ap, format);
  1056.     fprintf (stderr, "FATAL:");
  1057.     vfprintf(stderr, format, ap);
  1058.     fprintf(stderr, "\n");
  1059.     va_end(ap);
  1060.     exit(1);
  1061. }
  1062. #endif /* #ifdef TEST */
  1063.